1. Field of the Invention
This invention generally relates to cache storage in a multilevel data storage hierarch and more particularly to management of the available cache storage.
2. Description of the Prior Art
The performance of data processing systems has improved dramatically through the years. While new technology has brought performance improvements to all functional areas of data processing systems, the advances in some areas have outpaced the advances in other areas. For example, advancements in the rate at which computer instructions can be executed have far exceeded improvements in the rate at which data can be retrieved from storage devices and supplied to the instruction processor. Thus, applications that are input/output intensive, such as transaction processing systems, have been constrained in their performance enhancements by data retrieval and storage performance.
The relationship between the throughput rate of a data processing system, input/output (I/O) intensity, and data storage technology is discussed in "Storage hierarchies" by E. I. Cohen, et al., IBM Systems Journal, 28 No. 1 (1989). The concept of the storage hierarchy, as discussed in the article, is used here in the discussion of the prior art. In general terms, the storage hierarchy consists of data storage components within a data processing system, ranging from the cache of the central processing unit at the highest level of the hierarchy, to direct access storage devices at the lowest level of the hierarchy. I/O operations are required for access to data stored at the lowest level of the storage hierarchy.
Caching takes place at various levels of the storage hierarchy. An instruction processor cache caches data stored in main memory and main memory essentially caches data stored in secondary storage. A second level cache between an instruction processor cache and the main memory is used in the 2200/900 Series data processing system from Unisys Corporation. Secondary storage devices, such as disk subsystems, are also available with a cache between the electromechanical storage device and the main memory of data processing system.
The cache at each level of the hierarchy requires management logic to control the allocation of available cache storage. The cache management scheme chosen will impact the performance enhancement sought by caching. Two common cache replacement methods are used to select an allocable portion of cache storage in which to store data when a cache miss is encountered. The round robin replacement method is simple to implement, however, the cache hit rate may suffer due to its simplicity. On the other hand, selecting the least-recently-used entry in the cache to replace may enhance the hit rate at the expense of operational complexity.
A round robin replacement scheme for a cache store is described in U.S. Pat. No. 4,195,343 to Thomas F. Joyce. The round robin method constitutes a first-in first-out policy for cache replacement. Implementation is simple because the logic need only cycle through the available cache store in selecting a location for replacement. A disadvantage to this method is that it ignores the possibility that once a location is referenced, is it likely to be referenced again. Therefore, it would be desirable not to replace recently referenced locations to avoid reading the data from storage and writing it to the cache store. The least-recently-used method addresses this concern.
U.S. Pat. No. 4,636,946 to Michael H. Hartung and Gerald E. Tayler describes the use of a least-recently-used method for cache replacement in a caching a disk storage apparatus. A list of the cache store locations is maintained and is ordered from least-recently-used to most-recently-used. Generally, when a location in the cache store is to be replaced, the least-recently-used location is selected. A drawback to this method is that each time a location in the cache store is referenced, the referenced location must be moved to the most recently used end of the ordered list of cache store locations.
Determining when to write updated cache store locations back to storage, commonly referred to as destaging, is also an important aspect of cache management. As pointed out in U.S. Pat. No. 4,636,946, it is desirable to move data from cache to storage before the cache storage space is needed for allocation. In addition, U.S. Pat. No. 4,636,946 teaches scanning the least-recently-used list for modified data in the cache to be moved to a backing retentive store. The patent does not teach destage control where the backing store to which data is to be destaged is not directly accessible by the cache control.